//package personal.abandoned;
//
//
//import personal.scanner.ScannerFiniteAutomata;
//import personal.util.Utilities;
//import personal.util.Graph;
//import personal.util.IdAllocter;
//
//import java.util.*;
//
///**
// * 将 DFA 最小化
// *
// * @author 陈渤林
// */
//public class DFAMinimizer {
//    /**
//     * 用于自动分配子集 id
//     */
//    public IdAllocter alloc = null;
//    /**
//     * 状态转移集合，即状态转移的所有方式
//     */
//    private Set<Integer> transitions = null;
//    /**
//     * 状态转移图
//     */
//    ScannerFiniteAutomata dfa = null;
//
//    /**
//     * 将传入的集合划分得更小
//     */
//    private List<Set<Integer>> divide(final Set<Integer> init) {
//        List<Set<Integer>> ret = new ArrayList<Set<Integer>>();
//        // 检查所有转移是否相同
//        boolean have_same_out = true;
//        for (int t : this.transitions) { // 对于转移集合中的每一个转移 t
//            // 记录所有转移结果的来源
//            Map<Set<Integer>, Set<Integer>> v_to_us = new HashMap<Set<Integer>, Set<Integer>>();
//            for (Integer u : init) { // 对于 init 集合中的每一个点 u
//                Set<Integer> v = Utilities.moveByTransit(this.dfa, new TreeSet<Integer>(Arrays.asList(u)), t); // v = move(u, t)
//                v_to_us.putIfAbsent(v, new TreeSet<Integer>());
//                v_to_us.get(v).add(u);
//            }
//            // 这些来源按照转移结果分组后，构成 init 的一个划分
//            if (v_to_us.size() > 1) { // init 的 t 转移具有可分辨性
//                for (Set<Integer> key : v_to_us.keySet())
//                    ret.add(v_to_us.get(key));
//                have_same_out = false;
//                break; // 划分完毕
//            }
//        }
//        if (have_same_out) { // 如果所有转移均是不可分辨的
//            ret.add(new TreeSet<Integer>(init)); // 那么是不可分辨的，st 不必继续划分
//        }
//        return ret;
//    }
//
//    /**
//     * 将传入的集合划分划分得更小，是 divide 的驱动函数
//     */
//    private List<Set<Integer>> divide(final List<Set<Integer>> init) {
//        List<Set<Integer>> ret = new ArrayList<Set<Integer>>();
//        for (Set<Integer> st : init) // 检查划分的每一个集合 st
//            ret.addAll(this.divide(st));
//        return ret;
//    }
//
//    /**
//     * 初始化划分集合
//     */
//    private List<Set<Integer>> initPartition() {
//        // 初始化集合划分，将节点集合划分为可接受、不可接受
//        List<Set<Integer>> partition = new ArrayList<Set<Integer>>();
//        Map<Integer, Set<Integer>> buckets = new HashMap<Integer, Set<Integer>>();
//        partition.add(new TreeSet<Integer>()); // unaccept_bucket
//        // 遍历所有节点编号
//        for (int i = this.dfa.getStartId(); i <= this.dfa.getSize(); ++i) {
//            if (!this.dfa.isAcceptable(i)) {
//                partition.get(0).add(i); // 向 unaccept_bucket 放入当前节点
//            } else {
//                int id = this.dfa.getAcceptNodes().get(i); // 取节点编号的接受值，不接受则会抛异常
//                buckets.putIfAbsent(id, new TreeSet<Integer>()); // 如果第一次出现，那么添加空集
//                buckets.get(id).add(i); // 向对应的集合放入当前节点 i
//            }
//        }
//        // 将 buckets 中的集合逐个放入划分中
//        for (Map.Entry<Integer, Set<Integer>> bucket : buckets.entrySet())
//            partition.add(bucket.getValue());
//        return partition;
//    }
//
//    /**
//     * 传入 dfa，将其最小化。另外，这会将参数绑定到成员内
//     *
//     * @param dfa         传入的 dfa
//     * @param transitions 字母表
//     * @return 最小化的 dfa
//     */
//    public ScannerFiniteAutomata minimize(final ScannerFiniteAutomata dfa, final Set<Integer> transitions, int startId) {
//        this.transitions = transitions; // 绑定指定转移集合
//        this.dfa = dfa; // 绑定指定 dfa
//
//        List<Set<Integer>> partition = new ArrayList<Set<Integer>>(); // 初始为空集
//        List<Set<Integer>> nex_partition = initPartition(); // 初始划分
//        // 缩小划分，直至划分最小
//        while (!partition.equals(nex_partition)) { // 还能划分得更小
//            partition = nex_partition;
//            nex_partition = divide(partition); // 尝试将其划分
////        if (!isOK(partition, dfa.n)) throw new IllegalArgumentException("划分是错误的");
//        }
//        // 记录相关信息
//        return recordBy(partition, startId);
//    }
//
////    private boolean isOK(List<Set<Integer>> partition, int num) {
////        Map<Integer, Boolean> cnt = new HashMap<Integer, Boolean>();
////        for (Set<Integer> s : partition) {
////            for (Integer u : s) cnt.put(u, true);
////        }
////        return cnt.size() == num;
////    }
//
//    /**
//     * 通过传入的集合划分，生成最小化的 dfa
//     */
//    private ScannerFiniteAutomata recordBy(List<Set<Integer>> partition, int start_id) {
//
//        this.alloc = new IdAllocter(start_id);
//        ScannerFiniteAutomata ret = new ScannerFiniteAutomata();
//        // 生成一张从节点编号到子集编号的映射表，SetIdOfNode[i] 表示节点 i 的子集编号
//        int[] SetIdOfNode = new int[this.dfa.getSize() + 5];
//        // 对划分中的每一个子集进行编号
//        for (Set<Integer> setU : partition) // 编号 start_id 先给开始节点
//            if (setU.contains(start_id)) this.alloc.getId(setU);
//        for (Set<Integer> setU : partition) {
////            int idOfSetU = this.alloc.getId(setU); // 子集编号
//            for (Integer u : setU)
//                SetIdOfNode[u] = this.alloc.getId(setU); // 设置 u 的子集编号
//        }
//
//        for (Set<Integer> setU : partition) { // 对于 partition 中编号为 idOfSetU 的子集，考虑 partition[idOfSetU][0] 的所有转移
////            int idOfSetU = this.alloc.getId(setU); // 集合 su 的编号
//            // 更新出边
//            // 先将边放入 map 过滤，并检测可能的冲突
//            Map<Integer, Integer> buckets = new HashMap<Integer, Integer>(); // <w, v> 通过 w 到达 v
//            for (Integer u : setU) { // 遍历 su 中的每个节点 u
//                if (this.dfa.getOutEdgeAdjacencyList().get(u) == null) // u 没有出边
//                    continue;
//                for (Graph.Node node : this.dfa.getOutEdgeAdjacencyList().get(u)) { // 对于 u 出边 v
//                    int w = node.w, v = node.v;
//                    Integer preV = buckets.putIfAbsent(w, SetIdOfNode[v]); // 一条从 idOfSetU 到 SetIdOfNode[v] 的边
//                    if (preV == null) continue;
//                    if (preV != SetIdOfNode[v]) {
//                        String tmp = String.format("dfa 最小化时检测到转移冲突！从集合 %d 通过 %c 转移，原先转移到 %d，现在 %d", this.alloc.getId(setU), w, preV, SetIdOfNode[v]);
//                        throw new IllegalArgumentException(tmp);
//                    }
//
//                }
//            }
//            // 把 map 中的边放入 ret 中
//            for (Map.Entry<Integer, Integer> tmp : buckets.entrySet()) {
//                int u = this.alloc.getId(setU), v = tmp.getValue(), w = tmp.getKey();
//                ret.addEdge(u, v, w);
//            }
//
//            // 标记可接受节点
//            Set<Integer> acceptablePartOfSetU = Utilities.getIntersectionSet(setU, this.dfa.getAcceptNodes().keySet()); // 取交集
//            if (!acceptablePartOfSetU.isEmpty()) { // SetU 是 mindfa 的可接受节点
//                int acceptValue = this.dfa.getAcceptNodes().get(acceptablePartOfSetU.iterator().next()); // 接受值是 us 的代表的接受值
//                ret.registerAcceptableNode(this.alloc.getId(setU), acceptValue);
//            }
//        }
//        ret.setStartId(start_id);
//        return ret;
//    }
//}
